package 纯数组;

import 我的JDK基础数据结构.HashMap.HashMap;

import java.util.Map;

public class No560和为K的子数组 {

    /**
     * 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
     *
     * 示例 1 :
     * 输入:nums = [1,1,1], k = 2
     * 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
     * 说明 :
     * 数组的长度为 [1, 20,000]。
     * 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
     */

    /**
     * 一般解法: 双重for,左指针不移动
     * 优良解法: 前缀和~~~
     */
    public int subarraySum(int[] nums, int k) {

        /**
         * 有负数元素存在,所以不能使用双指针!!!
         */

        Map<Integer, Integer> map = new HashMap<>();
        //前缀和为0的数量是1
        map.put(0, 1);
        int sum = 0;
        int result = 0;

        for (int i = 0; i < nums.length; i++) {
            /**
             * 查看前面的前缀和;
             * 思考一番:
             * 例子:1,2,3,2,3,4,5 target:5
             * [x]:0 [0-0]:1 [0-1]:3 [0-2]:6 [0-3]:8 [0-4]:11 [0-5]:16 [0-6]:21
             *
             * [2]-> [0-2]:6  6-3=3 有[0-1]的一个3,所以结果+1
             * [3]-> [0-3]:8  8-2=6 无6
             * [4]-> [0-4]:11 11-3=8 有[0-3]的一个8,所以结果+1
             * ...
             * 总结规律: 到[4]时加了,然后减去目标5等于8 表明减去当前位置,前面的和有没有等于8的,
             * 如果有,那么 和起点:[8]-[当前点]=5,很好的想法~~~
             * 简言之: sum[x]=6 sum[y]=11 sum[y]-5=sum[x]那么 sum[x]+5=sum[y],说明[x-y]的和就是5
             */
            sum += nums[i];
            if (map.containsKey(sum - k))
                result += map.get(sum - k);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }

        return result;
    }

    public static void main(String[] args) {
        No560和为K的子数组 n = new No560和为K的子数组();
        int[] arr = {1, 2, 3, 2, 3, 4, 5};
        int result = n.subarraySum(arr, 5);
        System.out.println(result);
    }

}
